package Aleehot100;

/**
 * ClassName: c030
 * Package: Aleehot100
 * Description: 24 - 两两交换链表的节点
 *
 * @Author BCXJ
 * @Create 2025/6/17 12:39
 * @Version 1.0
 * @Since 1.0
 */
public class c030 {
    public static void main(String[] args) {
        ListNode listNode1 = new ListNode(1);
        ListNode listNode2 = new ListNode(2);
        ListNode listNode3 = new ListNode(3);
        ListNode listNode4 = new ListNode(4);
        listNode1.next = listNode2;
        listNode2.next = listNode3;
        listNode3.next = listNode4;

        ListNode listNode = swapPairs2(listNode1);

    }

    static class ListNode {
        int val;
        ListNode next;

        public ListNode(int val) {
            this.val = val;
            next = null;
        }
    }


    /**
     * 递归的解法（官方） - 时间空间都为 O(n)
     *
     * @param head
     * @return
     */
    public static ListNode swapPairs(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode newHead = head.next;
        ListNode midNode = head.next.next;
        head.next.next = head;
        head.next = swapPairs(midNode);
        return newHead;
    }


    /**
     * 有限变量方法 - 时间O(n)，空间问O(1)
     * @param head
     * @return
     */
    public static ListNode swapPairs2(ListNode head) {
        if(head == null || head.next == null) {
            return head;
        }
        ListNode cur = head;
        ListNode curNext = head.next;
        head = head.next;
        ListNode mid = null, pre = null;
        // 交换
        while(cur != null && curNext != null) {
            mid = curNext.next;
            curNext.next = cur;
            cur.next = null;
            if(pre != null) {
                pre.next = curNext;
            }
            pre = cur;
            cur = mid;
            curNext = cur != null ? cur.next : null;
        }
        if(cur != null || curNext != null) {
            pre.next = cur;
        }
        return head;
    }
}
